本地差分隐私的工作形式——一种隐私模型，数据即使来自统计人员或学习者也是私密的，我们研究了隐私保证和所得到的统计估计量的效用之间的权衡。我们证明了包括互信息和KL散度在内的信息论量的界，它们作为量化隐私保护的函数影响估计率。当与Le Cam和Fano方法等minimax技术结合时，这些不等式允许在局部隐私约束下精确刻画统计速率。在这篇文章中，我们提供了两个典型问题族的处理方法：位置族模型中的均值估计和凸风险最小化。对于这些族，我们提供了与常数因子相匹配的总体数量估计的下界和上界，给出了实现该界的隐私保护机制和有效计算的估计量。
我们研究本地隐私的强设置，其中数据提供者不信任任何人，甚至不信任收集数据的统计人员。虽然本地隐私是严格的，但它是最古老的隐私形式之一，其本质形式可以追溯到Warner ，他提出局部隐私是对他所说的调查抽样中"回避回答偏差"的一种弥补。我们认为，理解这个经典场景中的minimax risk边界是深入理解其他隐私保护数据分析方法的自然第一步。
用数学来描述，根据某个分布抽取了样本 ，我们考虑估计分布参数的过程，该过程只能访问原始数据的"遮掩视图" . 样本和这个私有化随机变量通过一族条件分布建立了联系，由于该分布建立了两者联系的管道，因此我们将分布称之为信道分布（channel distribution）
我们的工作基于本地差分隐私的一般定义，该定义如下描述：对于一个隐私参数，我们称是的-本地差分隐私的遮掩视图，如果满足
其中，，上确界取，表示上的一个适当的-域
式并未约束作为的单次数据发布（a single release of data）：只要全集合是-差分隐私的，就可以由若干个有关的查询结果组成。在所有遮蔽数据点上信道分布的依赖性凸显了隐私提供机制的潜在交互性。我们还考虑了一种适用于非交互协议的简化，这种情况下是仅基于生成的，所以的界（bound）可以退化为
这些定义描述了一种“似是而非”的可否定性：无论发布了什么数据，它来自中的任一点的可能性都几乎相等。差分隐私提供了对数据集中是否存在数据的挖掘保护的保证，以及处理其他形式化问题的辅助信息、对手强度以及组合问题，为差分隐私提供了有力的论据。
尽管差分隐私为限制披露以及防止多种形式的隐私泄露提供了一种优雅的形式化定义，但它是一种严格的隐私举措并且对于统计实践来说或许也有些严格。事实上，Fienberg等人批判了差分隐私在发布列联表中的应用，他们认为已知的差分隐私数据发布机制会导致不可接受的性能下降。因此，他们主张在某些情况下诉诸较弱的隐私保障，以维持发布数据的效用和可用性。然而，也有一些结果更有利于差分隐私；例如，Smith 证明了在一些参数问题中，差分隐私的非局部形式可以被满足，同时对于不同的点估计量可以得到渐近最优的参数收敛率。Dwork和Lei的研究也表明，可以利用稳健估计量（在差分隐私的非局部形式中）进行精准的隐私推断。要解决这些观点的差异，我们需要调研特定方法是否具有最优性，从而可以对框架进行通用化评判，并权衡好隐私性和统计效率之间的关系。这就是本文的研究目标。
本文的主要贡献是提供了在局部隐私约束下求最小上界（minimax bounds）的通用技术，并举例说明了这些技术在计算两个典型问题的minimax rates方面的应用，这两个问题分别是（a）位置族的均值估计和（b）侧重于线性函数优化的凸风险（convex risk）最小化。我们现在概述我们的主要贡献，给相关工作一些pointers。因为我们minimax框架的正式定义和主要结果的展示可以更深入地比较当前的工作和以前的研究，我们对这一相关工作进行了广泛的讨论（见第六节）。简而言之，根据统计决策理论，minimax rates是用于估计总体数量（population quantities），（据我们所知）而最早的工作——尤其是提供下界的前提下——更侧重于样本数量估计。总体数量和样本数量的边界刻画有很大差异，这种差异驱动了统计推断领域的文献中的许多技术性工作。对于样本数量估计下界的最新工作，例如参见Beimel等人、Hardt和Talwar以及De的文章；而在总体数量估计上，Chaudhuri和Hsu也为某些基于两点估计量族的一维(总体)统计提供了一类下界。
许多获得极小极大界的标准方法都涉及信息论方法量（information-theoretic quantities），包括某些随机变量之间的互信息（mutual information）和可能生成数据的不同分布之间的KL散度（Kullback-Leibler Divergence）。相应地，我们的两个主要定理将隐私与这些信息论方法量联系起来。
特别地，设和表示两种分布，分别用于生成数据，对于，定义在上的边际分布（Marginal Distribution）
这里边表示根据推理算法和数据提供者使用的通信协议的前提下，以初始数据为条件，个样本在上的联合分布。式分布刻画了样本的互信息，而KL散度则是衡量差异性和minimax rates的关键指标。
考虑到这些量的中心地位，我们的主要结果可以更高层次的抽象概括：
定理1的本质可以描述为
该定理用一个基于差分隐私参数和的初始分布之间的变化距离来限制式定义的分布和之间的KL散度。
其中表示常数因子的不等关系‘；当，这个定理表明对于minimax rate的收敛值可以被经典的信息论方法确定，本地差分隐私的附加要求使得任何统计程序中的有效样本量从可以减少到至多。
第III - A节给出了该定理的形式说明，第III - B节给出的推论表明了minimax rate bounds的应用。我们在第III - C节中遵循这一思路，将这些结果应用于位置族（location family）模型的估计，给出了minimax rate 的上下界。与我们的分析一致，我们看到有效样本容量从减少到，但我们也看到private estimation在非紧空间上的一些显而易见的困难。事实上，相当可观的是，如果我们想要估计满足方差的随机变量的均值，估计的minimax rate就从下降到。
定理1适用于只保留单一维量的问题，但对于解决高维问题有一定困难。因此，我们给出了第二个主要结论（定理2）用于本质地解决维度较高的问题。在更高的层次上，它提供了证明下界所需的信息论方法量的广义变分上界，我们在此给出其应用的简要概述。给定式的多个分布，其中取值于某个大集合，表示数据上的一组可能的分布。我们定义平均分布。在例如Fano等人方法的信息论技术中，控制平均偏差大于是证明minimax rate下界的必要条件。定理2允许我们将元素的协方差结构与这个平均KL散度联系起来。因此，通过适当选择集合，我们得到对于某些维统计问题，有效样本容量可以从减少到。我们在第IV节给出定理2的陈述和推论，在第V节给出其在凸风险最小化问题中的应用。我们会给出了本文中所有结果的证明。
对于空间中的分布和，关于分布（分别具有相对应密度）绝对连续，定义之间的KL散度为
之间的总变化距离为
对于随机向量，设表示在和上的条件分布，分别表示和的边际分布，之间的互信息为
对于实数序列和，用表示存在一个全局数值型常量，使得对所有的都有，并且用表示 和。对于凸函数，我们用表示它在处的次微分（sub-differential）
我们首先建立起本文所使用的minimax框架；令表示样本空间上的一类分布，表示定义在上的函数。参数取值的空间取决于底层统计模型(例如,对于单变量均值估计,它是实线的子集)。令表示空间上的半度量（semi-metric），用来度量参数的估计误差。是一个非减函数且（例如）。
在经典设定下，统计学家可以直接放雯根据抽取的样本。本地隐私除此之外还有额外设定：一个条件分布，其将样本呢转换为在中取值的私有样本。基于观测值其目标是估计未知参数。估计器（estimator）是一个可测函数，描述为。我们用来评估这个估计器的质量。例如，对于且的单变量均值估计问题，这个误差度量就是均方误差。因此对于既定的条件分布，我们定义了minimax rate为
其中我们在所有分布上取上确界(最坏情况)，在所有估计器上取下确界。对于每个，我们还可以定义集合由所有保证本地隐私的条件分布组成。通过最小化所有的，我们得到了族的minimax rate为
该量是本文研究的中心对象：它刻画了在族上使用最佳可能估计器和本地私有条件分布，关于隐私参数的最优统计估计率。
证明minimax bounds标准的第一步是将一个估计问题（estimation problem）转化为一个测试问题（testing problem）。更确切地说，给定一个有限基数的指标集（index set），考虑中包含的一族分布。该族导出一个参数集合，如果对所有的，，则该集合是半度量中的填充。我们用这个族来定义规范假设检验问题（canonical hypothesis testing problem）：自然界随机均匀地选择一个随机变量，在选择的条件下，数据是从fold product distribution 中抽取所得。由本地隐私约束提供的额外twist是，对于给定的条件分布，我们通过对分布 （在非交互情况下,根据对进行采样）中的每一个进行采样生成一个新的随机向量。在选择的条件下，随机向量按照式定义的生成新的边际分布。
给定观测向量，目标是确定底层指标的值。测试函数是一个可测映射，其错误概率为，其中表示随机指标上的联合分布。从估计到测试的规约化保证了——对于任意非减函数，先前定义的minimax error下界为
其中下确界适用所有的测试函数。
在这种规约化之后，剩下的挑战是在潜在的多重假设检验问题中降低错误概率。这方面的技术有很多种，我们关注错误概率的两个界。当中只有两个值时，Le Cam不等式（例如l引理1或定理2.2）成立，在这种情况下
其中边际的定义如式所示。更一般地，Fano不等式给出了多重假设检验的界，如下所示
由于不等式和，我们的主要理论结果集中在如何控制总变化距离或互信息上。这使得我们可以证明minimax rate的精确下界。
首先，我们给出了本地隐私约束下对称KL散度的上界。下面我们给出Le Cam方法的一些结果。利用这些方法，我们得到了本地隐私下的更精确的minimax rate，用于估计分布均值。
许多统计问题依赖于定义在公共空间上的一对分布之间的比较。任一条件分布通过边缘化将这样一对分布转化为新对。我们的第一个主要结果给出了这两个诱导边际之间(对称) KL散度的界。这两个诱导边际是与条件分布和和之间的总变化距离相关的隐私参数的函数。
定理 1： 设是任意一个为提供差分隐私的条件分布。则对于上的任意两个分布和，诱导边际和满足
定理1的结果与Dwork等人的结果类似，其内容是对任意， ，由于凸性，我们可以得知，因为缺少变分范数项，其要弱于定理1。该范数项为，这对于总体估计的minimax的下界是至关重要的，其不仅提供了KL散度的一个界，定理1也表明了差分隐私在概率测度空间呈现出“收缩”表现。
我们现在要发展一个推论，该推论在本地隐私约束下对minimax理论会有实用的结果。假设，在条件下，通过分布独立同分布生成每个，形成一个随机向量。给定满足α本地隐私的条件分布，从中采样，形成随机向量。在的条件下，随机向量按照前面定义的测度进行分布生成。由于我们允许交互协议，即使我们强制执行本地隐私，这并不一定是product distribution。
推论 1： 对于任意保证本地差分隐私（式）的条件分布和任意一对分布和，有
对于在指标集上均匀分布的，
备注：
我们现在讨论定理1对于极小极大理论的一些结果，重点是为了便于在独立同分布采样模型上表示，即。我们证明，在Le Cam不等式中，α -本地差分隐私的price是有效样本量从减少到。对于是的函数的估计器，Le Cam方法的经典(非私有)版本适用于通常的minimax risk
Le Cam引理的一个版本断言，对于任意一对分布，使得，我们有
在本地私有的情形下，其中估计器必须只依赖于私有变量，我们度量私有minimax risk。通过将Le Cam方法应用于不等式 （以及Pinsker不等式）形式的一对分布和推论1，我们发现对于，有
通过与的比较，我们看到对于，本地差分隐私的效果是将有效样本量从减少到。
在本节中，我们举例说明利用私有版本的Le Cam不等式，研究location族的均值估计问题；除了展示minimax rate是如何随变化的，我们还揭示了一些有趣（或许令人不安）的实施本地差分隐私的效应。对于，考虑分布的族，使得，假设我们希望估计均值。我们刻画了欧氏距离下的私有minimax risk，如下
命题 1： 对于所有，minimax error 有界为
我们利用Le Cam不等式的私有断言加强式证明了这个结果的下界，并利用一个截断参数和Laplace噪声证明了这个结果的上界。
为了理解命题1，我们可以从有限方差随机变量()的设定开始考虑一些特殊情况。在非隐私设定（其中原始样本(中直接观测），样本均值的均方误差至多为。然而，当我们要求本地差分隐私时，命题1表明minimax rate减慢到。更一般地，对于任意，minimax rate尺度为为。当时，矩条件等价于有界约束，我们得到了更标准的参数率和有效样本容量从减少到。
在本节中，我们转向更一般和更有力的互信息上界。如前所述，定理1和推论1仅给出了互信息的成对上界。充分利用Fano不等式的一般性，需要对本地隐私下的互信息有更精细的上界，这也是本节的主要内容。在接下来的第V节中，我们将展示如何利用这个上界来推导本地隐私下某些凸风险最小化问题的minimax rate。
我们从定义开始。设是在某个有限集合上均匀分布的离散随机变量。对于一族分布，定义 混合体
根据互信息的定义，如果是从中均匀采样，并且在的条件下，随机变量具有分布 (在边际意义上)
以上是一个在我们的理论中起着重要作用的表述。同定义一样，任何条件分布也诱导出marginal族，以及与之相关联的混合分布。我们的目标是与互信息相关的上界量，其中随机变量是根据绘制的。
我们的上界是变分的：它涉及到有界函数的上的优化，其中我们记，并且
由于集合一般从上下文中明确，我们典型地省略了这种依赖性。最后，对于任意的，我们通过以下式子来定义线性泛函
有了这些定义，有以下结果：
定理 2 对于给定的，令对样本是差分隐私的。对于上的概率测度集合，
其中
我们还可以提供一个类似于推论1的结果，它允许我们应用在第II - A节中概述的minimax下界。对于这个推论，我们需要非交互式的本地隐私设置，其中每个私有变量仅依赖于。我们猜想它在完全交互的环境中成立，但考虑到众所周知的多重信道容量的特征化困难，这可能是很有挑战性的。
推论 2 设 在 中随机均匀分布，并且假定 ，样本 按照分布 独立采样，其中 。定义 和线性泛函 。若对每个 ，在设定式 中对 是 差分隐私的，则在定理 2的记号中，
至于常数因子，定理2从来不弱于定理1给出的结果，特别是推论1给出的互信息的界。事实上，注意到立即得到类似推论1的结果。
定理2和推论2将数据的随机扰动视图之间的互信息量与参数空间的底层填充的变分性质联系起来。推论2表明任何统计过程可用的信息都可以用填充集（packing set）的几何形状来控制。因此，定理2和推论2表明，如果我们能够找到一个集合，使得它生成的线性泛函的和具有良好的"谱"性质——当取型空间上的上确界时，它是一个小算子范数，那么我们可以给出更精确的结果。
最小化风险泛函的概念起源于Wald的开创性工作，是决策理论统计学的核心。在实际中，最小化凸函数是最有吸引力的，因此凸风险最小化提供了一个自然的设置来说明定理2的作用。在早期的工作中，我们通过计算互信息的鞍点来研究凸风险最小化下的隐私保护问题。此前的工作与此有很大不同。在我们早期的文章中，数据提供者被要求是"最优私有的" ，并且只能通过发送一个损失函数的模糊梯度来进行通信。这里给出的结果更泛化，证明也更直接，因为定理2允许我们避开在前面的文章中起到核心作用的鞍点，并且我们对机制(即信道分布Q)进行除了本地差分外的任何限制。
在本节中，我们给出了线性泛函极小化的minimax收敛速度，尽管我们的下界也适用于一般的凸风险最小化问题。在更一般（非线性）的情况下，我们知道如何仅使用交互式随机梯度方法来获得下界，因此在高维情况下理解交互性和minimaxity之间的联系可能是有趣的。
给定一个紧的凸集，我们的目标是找到一个参数值在损失函数下取得较好的平均性能。这里衡量参数向量在样本上的表现，对是凸的。我们通过风险函数来度量的期望性能
式中：其期望取空间上的某个未知分布。用表示基于扰动样本的估计器，我们显著地量化了收敛到的速率是样本数量和发布的隐私数据相对于初始样本所保留的隐私数目的函数。
为了说明我们的结果，我们需要一些与函数类和风险相关的定义。
定义 1 （(一致) Lipschitz连续性）对于给定的，函数关于范数是Lipschitz连续的，如果
如果不等式对所有都成立，则损失函数是一致Lipschitz连续的。
Lipschitz条件等价于范数次微分的有界性条件，其中 对任意向量，我们有。我们用作为这个条件的简写表示。
现在我们转向在凸风险最小化的背景下研究的minimax error。通常，表示接收到个私有样本后对的最小估计器。excess risk为
（这是loss和半度量在此设定下的模拟）。令表示损失函数的集合，其中对于上的分布，集合表示属于的损失。然后由期望excess risk给出minimax error
其中，期望取自随机样本和，下确界取自所有推理方法和非交互式本地差分隐私分布。
我们现在刻画本地隐私下凸风险最小化问题的minimax rate。我们的每个命题都考虑了域上的凸的Lipschitz连续损失函数的最小化问题。
我们的第一个下界适用于一类关于范数的Lipschitz函数，其中优化发生在球上。在陈述我们的minimax界时，我们使用线性损失的集合：我们定义为损失函数集合，存在使得且。 该类包含在一致连续凸函数的集合中，因此它的下界是更泛化的界。我们有如下的minimax rate：
命题 2 对于一类损失函数 和隐私参数 ，有
命题2给出了minimax rate直到数值型常量的精确刻画。类的非隐私minimax rate为
通过与不等式的比较，我们发现本地差分隐私对minimax rate具有维度依赖（dimension-dependent）效应：有效样本量不再像第III节那样简单地从减少到，而是从减少到。实际上，要求差分隐私在高维中是一个严格的约束：由于所有维度都必须被一致保护，因此收敛速度会受到明显的惩罚。
对于更大的域类和相关的优化函数，我们也可以给出一个结果。事实上，考虑损失函数类集合，定义为凸，其中是一致连续的，对于。我们定义为中的线性泛函。然后我们有以下结果，它捕捉了范数球形域上线性泛函优化的收敛速度。
命题 3 对于loss函数类 ，其中 且隐私参数 ，有
对于loss函数类，如果
与命题2一样，不等式给出了紧于常数因子的私有minimax rate的刻画。损失函数类的非私有minimax rate为。本地隐私带来的好处同样是维度依赖因子对有效样本量的缩减。
在本节中，我们简述了如何使用简单实用的算法来获取命题3的匹配上界——即随机梯度下降——伴随着"右"型随机扰动来保证本地差分隐私。在线性情况下，这些算法不具有交互性，需要本地对样本进行扰动；在更一般的凸情况下，这些算法需要交互隐私机制，因为它们迭代地处理数据。然而，我们确实得到了一般凸情形的匹配上界，这导致了一个有趣的开放性问题，即在非线性环境中交互性的作用。
给定一个初始化，随机梯度算法产生一个随机迭代序列如下，在迭代时，保持估计量并得到一个随机次梯度，期望。用这些量来update估计量
其中是更新步长（即学习率）。
可实现方案的第二个组成部分是满足本地差分隐私的条件分布。我们通过扰动随机向量来构造，从而构造满足的合适的随机向量 。我们使用一个包含标量界的特定的采样策略，我们后面会指定。此外，我们定义了偏差概率，并设是一个伯努利随机变量。
私有抽样方法 给定的向量，令 ，概率为；，概率为。关于样本的集合
对于任意满足的向量，采样策略是差分隐私的。通过对随机样本进行归一化处理，可以高效地实现。
我们的方法是采用采样策略结合随机梯度下降法，开发凸风险最小化的本地差分隐私算法。在每种情况下，我们的算法如下：在算法迭代时，计算第个数据的随机梯度，然后根据分布采样一个向量，其性质为。然后利用这些差分隐私随机梯度估计进行梯度下降。注意到在线性情形，即，则与无关，从而对的采样是非交互的。
我们现在陈述一个详细的收敛结果，该结果达到了命题3中的界：
引理 1 假设 ，对于某个 ，关于 范数是L - Lipschitz的，且 。令 从随机梯度向量 开始，按照采样方案生成
随机梯度下降达到收敛速度
为了得到一个与命题3相匹配的上界，我们注意到，如果对于，损失是一致 - Lipschitz的，那么对于，共轭于，即，我们有。因此，采样策略自然适用。继续，我们注意到，如果对绝对常数有，则有。因此，引理1意味着
这就是命题3中的界。顺便指出，在梯度向量中加入适当大小的拉普拉斯噪声，给出了差分隐私算法，但比命题3要求的维数依赖性更差。
在开发本地和非本地环境下的差异化私有机制方面，已有大量工作。我们首先回顾了差分隐私的标准定义，即输出空间为的机制是差分隐私的当且仅当
式中：表示集合间的汉明距离。本地隐私强于差分隐私。
在隐私保护数据分析的工作中，作者试图刻画什么是可估计的，什么是最优的估计机制。与我们工作相关的是Kasiviswanathan等人，他们关注于Probably-Approximately-Correct( PAC )学习问题，并证明了Kearns的统计查询模型和本地学习在样本容量的多项式变化下是等价的。在我们的工作中，我们关心的是推理过程性能的更精细的度量- -真实的收敛速度。
在不同的工作中，一些研究人员考虑了与我们的minimax准则类似的数量，但他们关注的是样本数量的最优估计，即用表示估计的样本量——如样本均值——它们侧重于度量风险的形式
式中：根据绘制，下确界取自差分私有信道。据我们所知，以前大多数关于隐私下界的文献都集中在从样本估计量中确定最坏情况下的误差，而不是总体数量。
这些量之间的关系正是统计推断理论所要解决的。样本风险与极大极小风险有本质的区别；对总体数量的估计是推理任务的目标。此外，样本风险的下界并不意味着的估计速率有界：样本风险要求在上有上确界。在某些情况下，我们可以多说。具体而言，假设满足三角不等式。则对任意估计量，
我们发展了两个不等式：定理1和定理2允许我们给出在本地私有环境下估计总体数量的minimax rates。我们认为，我们的结果提供了关于获取隐私的成本的洞见。特别地，这里的结果显示了当数据提供者希望在数据发布之前保证自己的隐私时，以增加样本复杂度的形式，所得到的好处或付出的代价。这种保证虽然是可取的，但对于取样代价大、样本容量较小或维度很高的问题往往是站不住脚的。在量化这些权衡时，我们希望我们的minimax bounds能够启发更多可操作的统计程序，并为披露风险的讨论提供参考。
下一个问题是我们能在多大程度上使这些结果适应(非本地)差异私有场景。私人估计量的有效样本容量为，而样本估计的下界具有相似的缩放性。类似的信息论方法是否能保证我们所提出的，以及总体估计的下界是什么，仍然是悬而未决的问题。